import collections


class Solution(object):
    def lexicalOrder(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        stack = [[1, 1]]
        out = [1]
        while stack:
            if stack[-1][0] * 10 <= n:
                stack.append([stack[-1][0] * 10, 0])
                out.append(stack[-1][0])
            else:
                if stack[-1][0] + 1 <= n and stack[-1][1] + 1 <= 9:
                    stack[-1] = [stack[-1][0] + 1, stack[-1][1] + 1]
                    out.append(stack[-1][0])
                else:
                    while stack and (stack[-1][0] + 1 > n or stack[-1][1] + 1 > 9):
                        stack.pop()
                    if stack:
                        stack[-1] = [stack[-1][0] + 1, stack[-1][1] + 1]
                        out.append(stack[-1][0])
        return out


data = Solution()
n = 13
print(data.lexicalOrder(n))
